package com.github.hgkmail.hello.leetcode101.sort;

import java.util.*;
import java.util.function.Consumer;

//1.使用 HashMap + HashMap(或数组、list)
//2.使用 HashMap + 优先队列
public class LC347TopKFrequentElements {
    public int[] topKFrequent(int[] nums, int k) {
        if (nums.length<=0) {
            return new int[]{};
        }
        Map<Integer, Integer> counts = new HashMap<>();
        //统计数字频数
        for (int i = 0; i < nums.length; i++) {
            counts.put(nums[i], counts.getOrDefault(nums[i], 0)+1);
        }
        //按频数排序
        PriorityQueue<Map.Entry<Integer, Integer>> heap = new PriorityQueue<>(nums.length, new Comparator<Map.Entry<Integer, Integer>>() {
            @Override
            public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {
                return o2.getValue()-o1.getValue(); //pq是小顶堆，这里求前k大，因此要反过来
            }
        });
        counts.entrySet().forEach(heap::offer);
        int[] res = new int[k];
        int sz=0;
        while (sz<k && !heap.isEmpty()) {
            res[sz]=heap.poll().getKey();
            sz++;
        }

        return res;
    }
    public static void main(String[] args) {
        System.out.println(Arrays.toString(new LC347TopKFrequentElements().topKFrequent(new int[]{1,1,1,2,2,3,3,3,3}, 2)));
    }
}
